최근접 이웃 알고리즘

거리 측정 방법은 최근접 이웃 알고리즘의 핵심으로, 데이터 포인트 간의 유사성 또는 비유사성을 수치화하는 기준을 정의한다. 적절한 거리 함수 선택은 알고리즘의 성능에 직접적인 영향을 미친다. 가장 일반적으로 사용되는 거리 측정법은 다음과 같다.

데이터의 특성과 문제의 맥락에 따라 적합한 거리 척도를 선택해야 한다. 예를 들어, 고차원 공간에서는 차원의 저주 현상으로 인해 유클리드 거리의 효용성이 떨어질 수 있으며, 이 경우 코사인 유사도가 더 강건한 결과를 제공할 수 있다. 또한, 모든 특성이 동일한 스케일을 가지지 않는다면, 거리 계산에 앞서 정규화나 표준화와 같은 데이터 전처리 과정이 필수적이다.

k-NN 알고리즘에서 k 값은 가장 중요한 하이퍼파라미터 중 하나이다. 이 값은 새로운 데이터 포인트의 클래스나 값을 예측할 때 참고할 이웃 샘플의 개수를 결정한다. k 값이 너무 작으면(예: k=1) 과적합이 발생하여 노이즈나 이상치에 매우 민감해진다. 반대로 k 값이 너무 크면(예: k=전체 데이터 샘플 수) 과소적합이 발생하여 결정 경계가 지나치게 평탄해져 모델의 복잡성을 잃게 된다[2]. 따라서 적절한 k 값을 선택하는 것은 모델의 일반화 성능을 높이는 핵심 과제이다.

일반적으로 k 값은 홀수로 선택하여 다수결 투표 시 동점을 방지한다. 최적의 k 값을 찾기 위한 가장 일반적인 방법은 교차 검증을 사용하는 것이다. 데이터를 훈련 세트와 검증 세트로 나눈 후, 다양한 k 값(예: 1부터 20까지의 홀수)에 대해 모델을 훈련시키고 검증 세트의 정확도나 오차를 측정한다. 가장 높은 성능을 보이는 k 값을 최종 선택한다. 이 과정은 그리드 탐색과 같은 체계적인 하이퍼파라미터 튜닝 기법으로 자동화될 수 있다.

k 값 선택에 영향을 미치는 요인은 다음과 같다.

데이터의 특성에 따라 적절한 k 값의 범위가 달라진다. 데이터의 차원이 매우 높은 경우(차원의 저주)나 클래스 간 경계가 뚜렷한 경우 상대적으로 작은 k 값이 효과적일 수 있다. 반면, 데이터에 노이즈가 많거나 클래스 간 중첩이 심한 경우 더 큰 k 값을 선택하여 평활화 효과를 얻는 것이 유리하다.

k-NN (k-Nearest Neighbors)는 최근접 이웃 알고리즘의 가장 대표적이고 기본적인 형태이다. 이 알고리즘은 분류와 회귀 문제 모두에 적용되며, 이름 그대로 새로운 데이터 포인트의 클래스나 값을 예측하기 위해 그 주변의 가장 가까운 k개의 데이터 포인트(이웃)를 찾아 활용한다.

분류 문제에서 k-NN은 일반적으로 다수결 투표 방식을 사용한다. 새로운 샘플이 주어지면, 사전에 정의된 거리 측정 방법(예: 유클리드 거리)을 사용하여 학습 데이터셋 내 모든 샘플과의 거리를 계산한다. 그 후 거리가 가장 가까운 상위 k개의 샘플을 선택하고, 이 k개 이웃의 클래스 레이블 중 가장 빈번하게 나타나는 클래스로 새로운 샘플을 분류한다. 예를 들어, k=5일 때 5개의 가장 가까운 이웃 중 3개가 'A' 클래스, 2개가 'B' 클래스라면, 새로운 샘플은 'A' 클래스로 할당된다.

회귀 문제에서는 분류와 유사하게 k개의 가장 가까운 이웃을 찾은 후, 이들의 목표값(연속적인 수치)의 평균을 계산하여 새로운 샘플의 예측값으로 사용한다. 이는 주변 이웃들의 값을 지역적으로 평균화하는 효과를 가진다.

k 값은 알고리즘의 핵심 하이퍼파라미터로, 모델의 복잡도와 성능에 직접적인 영향을 미친다. 일반적으로 작은 k 값(예: k=1)은 데이터의 지역적 패턴과 노이즈에 민감해 복잡한 결정 경계를 만들지만 과적합될 위험이 있다. 반대로 큰 k 값(예: k=20)은 더 많은 이웃을 평균화하므로 결정 경계가 부드러워지고 과적합을 줄일 수 있지만, 지역적 패턴을 지나치게 일반화하여 과소적합될 가능성이 있다. 적절한 k 값은 교차 검증 등을 통해 데이터에 맞게 선택해야 한다.

Radius Neighbors는 최근접 이웃 알고리즘의 주요 유형 중 하나로, 고정된 반경(radius) 내에 있는 모든 데이터 포인트를 기반으로 예측을 수행한다. 이 방법은 k-NN (k-Nearest Neighbors) 알고리즘이 고정된 수(k)의 이웃을 찾는 것과 대조적이다. 사용자는 기준이 되는 거리 임계값(반경 r)을 설정하며, 질의 포인트로부터 반경 r 이내에 위치한 모든 훈련 샘플이 '이웃'으로 간주된다.

알고리즘의 동작 방식은 다음과 같다. 새로운 데이터 포인트가 주어지면, 미리 정의된 거리 측정 방법(예: 유클리드 거리)을 사용하여 해당 포인트로부터 반경 r 안에 있는 모든 훈련 데이터를 찾는다. 분류(Classification) 작업에서는 이 범위 내 이웃들의 다수결 투표를 통해 클래스 레이블을 결정한다. 회귀(Regression) 작업에서는 이웃들의 목표값 평균을 계산하여 예측값을 도출한다. 반경 내에 이웃이 하나도 존재하지 않는 경우, 알고리즘은 특별한 값(예: 분류에서는 미리 정의된 기본 클래스, 회귀에서는 훈련 데이터의 평균값)을 반환하거나 오류를 발생시킬 수 있다.

이 방법의 특징은 이웃의 수가 고정되지 않고 데이터의 지역적 밀도에 따라 동적으로 변한다는 점이다. 이로 인해 데이터 분포가 균일하지 않은 경우에 유용하게 적용될 수 있다. 예를 들어, 일부 지역은 데이터가 밀집되어 있어 반경 내에 많은 이웃이 존재하고, 다른 지역은 희소하여 적은 수의 이웃만 존재할 수 있다. 주요 하이퍼파라미터는 반경 r의 크기와 사용할 거리 측정 척도이다.

Radius Neighbors는 공간 데이터베이스 질의나 이상 탐지(Anomaly Detection)와 같이 특정 거리 내의 모든 객체를 찾아야 하는 응용 분야에서 자연스럽게 적용된다. 그러나 최적의 반경 값을 선택하는 것은 데이터에 대한 사전 지식이나 교차 검증을 통한 실험이 필요하다.

최근접 이웃 알고리즘을 분류 문제에 적용하는 것은 가장 일반적이고 직관적인 사용 사례 중 하나이다. 이 방법은 레이블이 지정된 훈련 데이터 세트를 바탕으로, 새로운 데이터 포인트의 클래스를 그 주변의 다수결 투표를 통해 결정한다.

분류 과정은 먼저 새로운 데이터 포인트와 모든 훈련 데이터 포인트 사이의 거리를 계산하는 것으로 시작한다. 일반적으로 유클리드 거리나 맨해튼 거리가 사용된다. 이후, 미리 설정된 k개의 가장 가까운 이웃(최근접 이웃)을 찾는다. 최종적으로 이 k개의 이웃들 사이에서 가장 빈번하게 나타나는 클래스 레이블을 새 데이터 포인트의 예측 클래스로 할당한다. k=1인 경우는 1-NN이라고 하며, 가장 가까운 단 하나의 이웃의 클래스를 그대로 따르게 된다.

k-NN 분류기의 성능은 여러 요인에 의해 크게 영향을 받는다. 적절한 k 값의 선택은 과적합과 과소적합 사이의 균형을 잡는 데 중요하다. 너무 작은 k 값(예: k=1)은 데이터의 지역적 노이즈에 매우 민감해지고, 너무 큰 k 값은 결정 경계를 과도하게 평활화하여 세부 패턴을 놓칠 수 있다. 또한, 모든 특성(Feature)이 동일한 스케일을 가지도록 하는 정규화나 표준화와 같은 데이터 전처리가 거리 계산의 정확도에 필수적이다. 거리 기반 알고리즘의 특성상, 특성의 스케일 차이가 크면 특정 특성이 거리 계산을 지배할 위험이 있다.

이 분류 방식은 결정 경계를 명시적으로 학습하지 않고, 필요할 때(예측 시) 훈련 데이터를 참조하는 게으른 학습의 전형적 예시이다. 이로 인해 훈련 단계는 빠르지만, 예측 단계의 계산 비용이 높으며, 대량의 훈련 데이터 저장이 필요하다는 특징을 가진다.

최근접 이웃 알고리즘을 회귀 분석 문제에 적용한 것을 k-NN 회귀(k-Nearest Neighbors Regression)라고 부른다. 분류 문제에서는 가장 가까운 이웃들의 다수결을 통해 클래스 레이블을 예측하는 반면, 회귀 문제에서는 이웃들의 목표값(보통 실수값)의 평균이나 가중 평균을 계산하여 예측값을 도출한다. 이는 근처에 위치한 데이터 포인트들의 출력값이 유사할 것이라는 국소성 가정(Locality Assumption)에 기반한다. 가장 일반적인 방식은 단순 평균을 사용하는 것이지만, 각 이웃까지의 거리의 역수를 가중치로 사용하는 가중 k-NN 회귀도 널리 활용된다[4].

k-NN 회귀의 성능은 k 값과 사용된 거리 함수에 크게 의존한다. k 값이 너무 작으면 과적합되어 잡음에 민감한 예측을 만들고, k 값이 너무 크면 과소적합되어 지역적 패턴을 포착하지 못하고 지나치게 평활화된 예측을 생성할 수 있다. 회귀 작업에 적합한 거리 측정법을 선택하는 것도 중요하며, 일반적으로 유클리드 거리나 맨해튼 거리가 사용된다. 이 알고리즘은 모델을 명시적으로 훈련하는 과정이 없어 게으른 학습기(Lazy Learner)로 분류되며, 모든 계산이 예측 시점에 이루어진다.

k-NN 회귀는 구현이 간단하고 직관적이라는 장점이 있지만, 예측 시 모든 훈련 데이터에 대한 거리 계산이 필요하여 대용량 데이터셋에서는 계산 비용이 높을 수 있다. 또한, 고차원 데이터에서는 차원의 저주로 인해 성능이 저하될 수 있으며, 결측값이 있는 경우 적절한 전처리가 선행되어야 한다. 주로 주택 가격 예측, 수요 예측, 지속형 사용자 행동 점수 예측 등 비교적 저차원이고 데이터 분포가 명확한 문제에 효과적으로 적용된다.

최근접 이웃 알고리즘은 사용자 간 또는 아이템 간 유사도를 기반으로 한 협업 필터링의 핵심 방법론으로 추천 시스템에 널리 적용된다. 기본 아이디어는 비슷한 취향을 가진 사용자들이 선호하는 아이템을 추천하거나, 사용자가 과거에 선호한 아이템과 유사한 다른 아이템을 추천하는 것이다. 이를 위해 사용자-아이템 평점 행렬이나 상호작용 데이터를 바탕으로 유클리드 거리나 코사인 유사도 등의 척도를 사용하여 가장 가까운 이웃을 찾는다.

사용자 기반 협업 필터링에서는 특정 사용자와 유사도가 높은 k명의 다른 사용자(최근접 이웃)를 선정한다. 이후 이 이웃들이 높은 평점을 준, 대상 사용자가 아직 평가하지 않은 아이템을 추천 후보로 계산한다. 반면, 아이템 기반 협업 필터링에서는 사용자가 과거에 긍정적으로 반응한 아이템과 유사한 다른 아이템을 찾아 추천한다. 아이템 간 유사도는 대개 많은 사용자들에 대한 평점 벡터를 비교하여 계산한다.

이 방식의 장점은 모델을 별도로 학습시킬 필요가 없는 지도 학습의 일종인 게으른 학습자 특성을 가지며, 결과의 해석이 비교적 직관적이다. 그러나 사용자 수와 아이템 수가 증가함에 따라 모든 쌍에 대한 유사도를 계산하는 비용이 급격히 커지는 확장성 문제를 가진다. 또한 새로운 사용자나 아이템에 대한 정보가 부족한 콜드 스타트 문제가 발생할 수 있다.

성능을 개선하기 위해 차원 축소 기법을 적용하거나, 효율적인 인덱싱 구조를 도입하여 최근접 이웃 탐색 속도를 높인다. 또한 평점 데이터의 희소성을 완화하기 위해 결측값을 보정하는 전처리 과정이 중요하다. 현대의 대규모 추천 시스템에서는 최근접 이웃 알고리즘이 단독으로 사용되기보다는 행렬 분해나 딥러닝 기반 모델과 함께 앙상블되거나 초기 단계의 후보 생성기로 활용되는 경우가 많다.

최근접 이웃 알고리즘의 성능은 차원의 저주 현상에 크게 영향을 받는다. 고차원 공간에서는 모든 데이터 포인트 간의 거리가 비슷해져 거리 기반 유사도 측정의 의미가 퇴색되고, 계산 복잡도가 급격히 증가하며, 과적합이 발생하기 쉽다. 따라서 고차원 데이터에 최근접 이웃 알고리즘을 적용하기 전에 차원 축소를 수행하는 것이 일반적이다.

차원 축소 기법은 크게 특성 선택과 특성 추출로 나눌 수 있다. 특성 선택은 원본 특성 중에서 가장 관련성이 높은 일부를 선택하는 방법이며, 필터 방법, 래퍼 방법, 임베디드 방법 등이 있다. 특성 추출은 원본 특성을 변환하여 새로운 저차원 특성을 생성하는 방법으로, 주성분 분석과 선형 판별 분석이 대표적이다. 주성분 분석은 데이터의 분산을 최대한 보존하는 직교 축을 찾는 비지도 학습 방법이며, 선형 판별 분석은 클래스 간 분산은 최대화하고 클래스 내 분산은 최소화하는 축을 찾는 지도 학습 방법이다.

차원 축소를 적용하면 데이터 저장 공간과 거리 계산 시간이 줄어들어 최근접 이웃 알고리즘의 효율성이 향상된다. 또한, 노이즈와 불필요한 정보가 제거되거나 압축되어 모델의 일반화 성능을 높이는 데에도 기여한다. 그러나 축소 과정에서 일부 정보가 손실될 수 있으며, 변환된 특성의 해석이 어려워질 수 있다는 점은 고려해야 한다.

최근접 이웃 알고리즘은 새로운 데이터 포인트에 대한 예측을 수행할 때 훈련 데이터 전체를 탐색해야 하므로, 데이터셋의 크기가 커질수록 계산 비용이 급격히 증가하는 문제가 있다. 이를 해결하기 위해 효율적인 검색을 지원하는 공간 분할 기반의 인덱싱 구조가 개발되었다. 대표적인 구조로 KD-Tree와 Ball Tree가 있다.

KD-Tree(k-dimensional tree)는 다차원 공간에서 데이터 포인트를 효율적으로 조직화하는 이진 트리 구조이다. 이 구조는 공간을 좌표축에 수직인 초평면으로 반복적으로 분할하여 구축된다. 각 내부 노드는 하나의 차원과 분할 지점을 가지며, 해당 차원을 기준으로 데이터를 두 개의 자식 노드(왼쪽/오른쪽)로 나눈다. 검색 시, 쿼리 포인트와 분할 경계면의 거리를 기준으로 탐색 범위를 제한하여 불필요한 전체 탐색을 피할 수 있다. KD-Tree는 차원이 낮을 때(예: 20차원 미만) 매우 효율적이지만, 차원이 증가할수록 성능이 저하되는 차원의 저주 문제에 취약하다.

Ball Tree는 데이터 포인트들을 중첩된 초구(hypersphere)로 묶어 계층적 트리를 구성한다. 각 내부 노드는 자식 노드에 속한 모든 포인트를 포함하는 가장 작은 공(ball)으로 표현된다. 검색 시, 쿼리 포인트부터의 거리와 각 노드의 공 반지름을 비교하여, 해당 공 내에 최근접 이웃이 존재할 가능성이 없는 노드는 탐색에서 제외한다. 이 방식은 고차원 공간에서도 KD-Tree보다 더 안정적인 성능을 보이는 경우가 많다. 두 구조의 선택은 데이터의 차원, 크기, 분포 및 응용 분야의 요구 사항에 따라 결정된다.

최근접 이웃 알고리즘의 성능은 데이터의 품질과 형태에 크게 의존한다. 따라서 모델을 적용하기 전에 적절한 데이터 전처리를 수행하는 것이 필수적이다. 주요 전처리 과정에는 정규화 또는 표준화, 결측치 처리, 이상치 탐지 및 처리, 그리고 특성 선택 또는 특성 추출이 포함된다.

거리 기반 알고리즘의 특성상, 정규화와 표준화는 가장 중요한 단계 중 하나이다. 서로 다른 스케일을 가진 특성들이 존재할 경우, 큰 값을 가진 특성이 거리 계산에 과도하게 영향을 미쳐 모델 성능이 저하될 수 있다. 예를 들어, '연봉'(단위: 천만 원)과 '나이'(단위: 세)를 함께 사용한다면, 연봉의 작은 차이도 나이의 큰 차이보다 거리에 더 큰 영향을 미치게 된다. 이를 방지하기 위해 최소-최대 정규화나 Z-점수 표준화 등을 적용하여 모든 특성을 동일한 스케일로 조정한다.

또한, 차원의 저주를 완화하고 계산 효율성을 높이기 위해 특성 선택이나 차원 축소를 고려할 수 있다. 주성분 분석이나 t-SNE 같은 기법을 사용해 관련성이 높은 특성만을 선택하거나 새로운 저차원 공간으로 투영하면, 모델의 성능과 속도를 모두 개선할 수 있다. 모든 전처리 단계는 훈련 데이터셋을 기준으로 파라미터(예: 평균, 표준편차, 최소/최대값)를 학습하고, 이를 검증 및 테스트 데이터셋에 동일하게 적용하여 데이터 누출을 방지해야 한다.

최근접 이웃 알고리즘의 성능은 여러 하이퍼파라미터의 설정에 크게 영향을 받는다. 가장 중요한 하이퍼파라미터는 k-NN에서 사용하는 이웃의 수를 결정하는 k 값이다. k 값이 너무 작으면 과적합이 발생하여 잡음이나 이상치에 민감해지고, 너무 크면 과소적합이 되어 결정 경계가 지나치게 평탄해져 모델의 정확도가 떨어진다[5]. 적절한 k 값은 데이터의 특성과 규모에 따라 달라지며, 보통 교차 검증을 통해 실험적으로 결정한다.

거리 측정 방법 또한 핵심적인 하이퍼파라미터이다. 유클리드 거리는 가장 일반적으로 사용되지만, 특성의 스케일 차이에 민감하다. 맨해튼 거리는 격자 구조의 데이터에 적합하며, 민코프스키 거리는 거리 측정의 일반화된 형태를 제공한다. 데이터의 특성에 따라 코사인 유사도나 해밍 거리와 같은 다른 척도를 선택할 수도 있다. 각 거리 척도는 데이터의 기하학적 구조를 다르게 해석하므로, 적절한 선택이 필요하다.

가중치 부여 방식도 튜닝 대상이다. 기본적인 k-NN은 모든 이웃에 동일한 가중치를 부여하지만, 거리에 반비례하는 가중치를 부여하는 방식이 더 나은 성능을 보이는 경우가 많다. 이를 통해 가까운 이웃의 의견을 더 강하게 반영할 수 있다. 또한, Radius Neighbors 알고리즘을 사용할 경우, 고정된 반경 값이 주요 하이퍼파라미터가 된다.

하이퍼파라미터 튜닝은 일반적으로 그리드 탐색이나 랜덤 탐색과 같은 체계적인 방법으로 수행된다. 이 과정에서 교차 검증을 통해 모델의 일반화 성능을 평가하는 것이 필수적이다. 최적의 파라미터 조합은 검증 세트에서 가장 높은 성능을 보이는 것으로 선택한다.